package com.everyday.practice.leetCode;

import java.util.*;

/**
 * @description: 超时了  无语
 * @author: zhengbo
 * @time: 2022/1/15 12:58
 */
public class Title15 {
    public static void main(String[] args) {
        Title15 title15=new Title15();
        int[] nums=new int[6];
        nums[0]=-1;
        nums[1]=0;
        nums[2]=1;
        nums[3]=2;
        nums[4]=-1;
        nums[5]=-4;
//        nums[6]=4;
//        nums[7]=-2;
//        nums[8]=0;
//        nums[9]=4;
//        nums[10]=0;
//        nums[11]=-2;
//        nums[12]=3;
//        nums[13]=1;
//        nums[14]=-5;
//        nums[15]=0;
        List<List<Integer>> list = title15.threeSum(nums);
        System.out.println(list);
    }

    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        if (nums.length>2){
            //先排个序
            sort(nums,0,nums.length-1);
//            Arrays.sort(nums);
            int bre1=nums[0]-1;
            for (int i=0;i<nums.length;i++){
                if (nums[i]+nums[nums.length-1]+nums[nums.length-2]<0){
                    continue;
                }
                if (nums[i]+nums[0]+nums[1]>0){
                    continue;
                }
                if (nums[i]>0){
                    break;
                }
                int b1=nums[i];
                if (bre1==b1){
                    continue;
                }
                int bre2=nums[0]-1;
                Map<Integer,Integer> map=new HashMap();
                for (int j=i+1;j<nums.length;j++){
                    int b2=nums[j];
                    if (b1+b2+nums[nums.length-1]<0){
                        break;
                    }
                    if (bre2==b2){
                        continue;
                    }
                    int bre3=nums[0]-1;
                    for (int x=j+1;x<nums.length;x++){
                        int b3=nums[x];
                        if (bre3==b3){
                            continue;
                        }
                        if (map.getOrDefault(b2,nums[0]-1)==b3
                                ||map.getOrDefault(b3,nums[0]-1)==b2){
                            continue;
                        }
                        if (b1+b2+b3==0){
                            List res=new ArrayList();
                            res.add(b1);
                            res.add(b2);
                            res.add(b3);
                            list.add(res);
                            bre1=b1;
                            bre2=b2;
                            bre3=b3;
                            map.put(b2,b3);
                            map.put(b3,b2);
                        }
                    }
                }
            }
        }
        return list;
    }


    public void sort(int[] arr,Integer start,Integer end){
        if (start<end){
            Integer sortIndex=sortIndex(arr,start,end);
            sort(arr,start,sortIndex-1);
            sort(arr,sortIndex+1,end);
        }
    }

    public Integer sortIndex(int[] arr,Integer start,Integer end){
        Integer temp=arr[start];
        while (start<end){
            while (start<end&&arr[end]>=temp){
                end--;
            }
            arr[start]=arr[end];
            while (start<end&&arr[start]<=temp){
                start++;
            }
            arr[end]=arr[start];
        }
        arr[start]=temp;
        return start;
    }
}
